群论

一.群

1.群的定义

对于一个集合 SS 和定义在这个集合上的二元运算 * , 满足:

  • 封闭性。 aS,bS\forall a \in S,b \in SabSa*b \in S

  • 结合律。 abc=a(bc)a*b*c=a*(b*c)

  • 单位元。 ϵS\exists \epsilon \in S , aϵ=ϵa=aa*\epsilon = \epsilon * a=a

  • 逆元。 aS\forall a \in S , bS\exists b \in S , ab=ϵa * b = \epsilon , 记作 aa'

那么称 (S,)(S,*) 为一个群。

值得注意的是,一个群的单位元和逆元都是唯一的

2.子群

G(S,)G(S,*) 为一个群,若 TST \subseteq S ,且 H(T,)H(T,*) 也为一个群,那么称 HHGG 的子群,记作 HGH \le G

3.陪集

左陪集:若群 HH 为群 GG 的一个子群,且对于 gGg \in GgH={ghhH}gH=\{gh|h \in H \}

同样可以定义右陪集。

注意陪集可能不包含单位元,不一定是群。


陪集的性质:

  1. H=gH|H|=|gH|
  2. ggHg \in gH
  3. gH=HgHgH=H \Leftrightarrow g \in H
  4. aH=bHab1HaH=bH \Leftrightarrow a * b^{-1} \in H
  5. aH=BHaHbH=aH \not= BH \Rightarrow aH \bigcap bH=\varnothing
  6. gGgH=G\displaystyle \bigcup_{g \in G} gH={G}

二.拉格朗日定理

[G:H][G:H]: GGHH 不同陪集的数量

G / H G~/~H~: GG 中所有 HH 的左陪集

有:

H×[G:H]=G|H|×[G:H]=|G|

证明:由陪集的性质 1、5、6 显然。

三.置换群

1.置换

对于集合 S={a1,a2an}S=\{a_1,a_2 \dots a_n\} , 一个置换 ff 可表示为:

f=(a1,a2,,anap1,ap2,,apn)f=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}

pp1n1\sim n 的排列,意义为将 aia_i 映射为 apia_{p_i}

f=(ap1,ap2,,apnaq1,aq2,,aqn),g=(a1,a2,,anap1,ap2,,apn)f=\begin{pmatrix} a_{p_1},a_{p_2},\dots,a_{p_n}\\ a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}, g=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}

f×g=f(g(x))=(a1,a2,,anaq1,aq2,,aqn)f \times g=f(g(x))=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}

称为置换的乘法。

2.循环置换

一种特殊的置换,其中:

f=(a1,a2,,an)=(a1,a2,,ana2,a3,,a1)f=(a_1,a_2,\dots,a_n)=\begin{pmatrix} a_1,a_2,\dots,a_n\\ a_2,a_3,\dots,a_1 \end{pmatrix}

任意一个置换都可以表示为若干不相交的循环置换的乘积,例如

(a1,a2,a3,a4,a5a3,a1,a2,a5,a4)=(a1,a3,a2)×(a4,a5)\begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2) \times (a_4,a_5)

将一个置换 ff 拆分的循环置换个数记为 c(f)c(f)

3.置换群

SS 包含所有的 n!n! 个不同 nn 元置换,G(S,×)G(S,\times) 为一个群,证明如下:

  • 封闭性。 两个 nn 元置换的乘积仍为 nn 元置换,包含于 SS
  • 结合律。置换的乘法有结合律。
  • 单位元。置换 (a1,a2,,ana1,a2,,an)\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_1,a_2,\dots,a_n\end{pmatrix},也称恒等置换。
  • 逆元。上下两行交换即可。

GG 的子群称作置换群。

四.Burnsied 引理 和 Pólya 定理

1.轨道稳定子定理

对于作用在集合 XX 上的群 GG 和集合 XX 的一个元素 xx

xx 的轨道:G(x)={g(x)gG}G(x)=\{ g(x) | g \in G\}

xx 的稳定子:Gx={gGg(x)=x}G^x=\{ g \in G| g(x)=x\}

这里 g(x)g(x) 为群作用的函数,例如上文提到的置换。


  1. GxG^xGG 的子群。

    证明:

    • 封闭性。 f(x)=x,g(x)=x,f×g=f(g(x))=xf(x)=x,g(x)=x,f \times g=f(g(x))=x,所以 f×gGxf \times g \in G^x
    • 结合律。显然。
    • 单位元。ϵ(x)=x\epsilon(x)=x,所以 ϵGx\epsilon \in G^x
    • 逆元。gG\forall g \in G,因为 g×g=ϵg\times g'=\epsilon , g(x)=ϵ(x)=xg(x)=\epsilon(x)=x,所以 g(x)=xg'(x)=xg(x)Gg'(x) \in G
  2. G(x)=[G:Gx]|G(x)|=[G:G^x]

    证明:

    对于 f(x)=g(x)f(x)=g(x) , f×g1=ϵf \times g^{-1}=\epsilon

    若有两个 f(x)=g(x),f×g1=x=ϵ(x)f(x)=g(x),f \times g^{-1} = x = \epsilon(x) ,所以 f×g1Gxf \times g^{-1} \in G^x , fGx=gGx\Rightarrow fG^x = gG^x , 反之亦然。

    即不同的 gg 对应不同的陪集。

    所以对于 G(x)G(x) 中的 gg , 构造对应陪集为 gGxgG^x

    感觉在伪证。


轨道稳定子定理:

G(x)×Gx=G|G(x)| \times |G^x|= |G|

证明:

因为 GxG^xGG 的子群,由拉格朗日定理得:

Gx×[G:Gx]=G|G^x| \times [G:G^x]=|G|

由性质2得:

Gx×G(x)=G|G^x| \times |G(x)| = |G|

证毕。

2.Burnside 引理

若一个置换群 GG 作用于 XX , X/GX/G 表示在群 GG 作用下 XX 的所有等价类的集合。(注意每个等价类也是一个集合,若两个元素在 GG 作用下可以转化则属于同一个等价类)

XgX^g 表示在 gg 的作用下不变的 XX 中元素的集合。

那么有:

X/G=1GgGXg|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g|

证明:

gGXg=xXGx=xXGG(x)=GxX1G(x)=GYX/GxY1G(x)=GYX/GxY1Y=GYX/G1=GX/G\begin{aligned} \sum_{g\in G} |X^g|&=\sum_{x \in X} |G^x| \\ &=\sum_{x \in X} \frac{|G|}{|G(x)|} \\ &=|G|\sum_{x \in X} \frac{1}{|G(x)|} \\ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|G(x)|} \\ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|Y|} \\ &= |G|\sum_{Y \in X/G}1 \\ &= |G||X/G| \end{aligned}

即:

X/G=1GgGXg|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g|

可以参考 oi-wiki 的例子

3.Pólya 定理

X/G=1GgGmc(g)|X/G|=\frac{1}{|G|}\sum_{g \in G} m^{c(g)}

证明:

由 burnside 引理发现,在 gg 作用下的不动点的充要条件是每一个循环置换里元素同色。

那么式子就很显然了。

五.例题

1.P4980 【模板】Pólya 定理

首先置换群 GG 包含的元素分别为: 旋转 11 个点,旋转 22 个点...旋转 nn 个点

不难发现,旋转 kk 个点的 c(g)=gcd(n,k)c(g)=\gcd(n,k),原因如下:

所有循环置换所包含的元素个数相同,均为 lcm(n,k)k\frac{\text{lcm(n,k)}}{k}。(旋转次数/旋转步长)

那么循环置换的个数便为 nlcm(n,k)k=gcd(n,k)\frac{n}{\frac{\text{lcm}(n,k)}{k}}=\gcd(n,k)

由 polya 定理得:

X/G=1ni=1nngcd(i,n)|X/G|=\frac{1}{n}\sum_{i=1}^n n^{\gcd(i,n)}

化简可得:

X/G=1ndnndφ(nd)|X/G|=\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d})

直接计算即可,复杂度 O(n34)\mathcal{O(n^{\frac{3}{4}})}

#include <cstdio>

const int Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return 1ll * x * Inv( y ) % Mod; }


int phi( int n ) {
    int Ans = n;
    for( int i = 2 ; i * i <= n ; i ++ )
        if( n % i == 0 ) {
            Ans = Ans / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    if( n > 1 ) Ans = Ans / n * ( n - 1 );
    return Ans;
}

int T , n;
int main( ) {
    scanf("%d",&T);
    while( T -- ) {
        scanf("%d",&n);
        int Ans = 0;
        for( int i = 1 ; i * i <= n ; i ++ )
            if( n % i == 0 ) {
                Ans = Add( Ans , Mul( Quick_pow( n , i ) , phi( n / i ) ) );
                if( i * i != n )
                    Ans = Add( Ans , Mul( Quick_pow( n , n / i ) , phi( i ) ) );
            }
        printf("%d\n", Div( Ans , n ) );
    }
    
    return 0;
}